package com.tree.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName com.tree.leetcode.array
 * Description: 438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

 * <使用说明>
 * </p>
 * @Author tree
 * @Date 1/26/24 10:16 PM
 * @Version 1.0
 */
public class FindAnagrams_438 {

    public static void main(String[] args) {
       String  s = "cbaebabacd", p = "abc";
        System.out.println( findAnagrams(s,p));
    }



    public static List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        //建立两个数组存放字符串中字母出现的词频，并以此作为标准比较
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        //当初始化S、P的滑动窗口， 滑动窗口的首位在s[0]处时 （相当于放置滑动窗口进入数组）
        for (int i = 0; i < pLen; ++i) {
            //记录s中前pLen个字母的词频
            ++sCount[s.charAt(i) - 'a'];
            //记录要寻找的字符串中每个字母的词频(只用进行一次来确定)
            ++pCount[p.charAt(i) - 'a'];
        }

        //判断放置处是否有异位词     (在放置时只需判断一次)
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        //开始让窗口进行滑动,    //开始让窗口进行滑动
        for (int i = 0; i < sLen - pLen; ++i) {
            //开始让窗口进行滑动
            //左边向右移动， 实际以前的位置需要减一，
            --sCount[s.charAt(i) - 'a'];
            //增加滑动后最后一位的词频（以此达到滑动的效果）
            //右边滑动， 实际新滑动的位置(i+pLen)需要加一
            ++sCount[s.charAt(i + pLen) - 'a'];

            //判断滑动后处，是否有异位词
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }

}
